package main

import "fmt"

// 定义链表节点
type CircularListNode struct {
	Val  int               //链表的数据域
	Next *CircularListNode //链表的指针域
}

// 添加操作：给循环链表追加节点
func (cl *CircularListNode) Append(val int) {
	if cl == nil {
		return
	}
	cur := cl
	//1. 移动指针变量到末尾节点
	for cur.Next != cl {
		cur = cur.Next
	}
	//2. 新节点追加到末尾节点
	newNode := &CircularListNode{Val: val}
	cur.Next = newNode
	newNode.Next = cl //更改末尾节点的指向
}

// 打印循环链表
func (cl *CircularListNode) Print() {
	if cl == nil {
		return
	}
	cur := cl.Next
	if cur == cl { //只有一个节点的情况
		fmt.Println(cur.Val)
		return
	}

	//1. 打印头节点
	fmt.Printf("%d ", cl.Val)
	//2. 遍历打印下一个节点
	for cur != cl {
		fmt.Printf("%d ", cur.Val)
		cur = cur.Next
	}
	fmt.Println()
}

// 删除操作，删除第k个节点（返回删除的节点）
func Remove(head *CircularListNode, k int) *CircularListNode {
	if head == nil || head == head.Next {
		return head
	}
	//情况1：删除的节点为头节点（当前节点）
	if k == 0 {
		cur := head
		//找到末尾节点
		for cur.Next != head {
			cur = cur.Next
		}
		cur.Next = head.Next //更改末尾节点的指针域
		return head
	}
	//情况2：删除的节点为 非头节点
	cur := head
	for i := 0; i < k-1; i++ {
		cur = cur.Next
	}
	tmp := cur.Next
	cur.Next = cur.Next.Next
	return tmp
}
func josephus(n, m int) {
	//1.  创建一个循环链表
	head := &CircularListNode{Val: 1}
	head.Next = head
	//2.  添加节点
	for i := 1; i < n; i++ {
		head.Append(i + 1)
	}
	fmt.Println("原始链表：")
	head.Print()

	fmt.Println("依次删除的元素：")
	//3. 依次删除链表节点
	for j := 0; j < n; j++ {
		delNode := Remove(head, m-1)
		fmt.Printf("%d ", delNode.Val)
		head = delNode.Next
	}
	fmt.Println()
}
func main() {
	//josephus(6, 5)
	//josephus(6, 1)
	josephus(41, 3)
}
